package main

import (
	"container/list"
	"fmt"
)

/*
*
核心结构: 哈希表+双向链表

取出:

	已存在
		更新链表，将本次取值的节点挪动至链表第一位，返回节点值
	不存在
		返回-1

放入:

	已存在
		将已存在的结点挪至链表第一位并更新值
	不存在
		首先判断是否达到cache最大个数，如果达到最大容量，则移除链表最后一个元素，同时从map中移除该元素
		接着将新的元素加入到链表和map中

注意
第一点: m中保存的是*list.Element，举个例子，Get操作需要从m中取出元素，并将元素挪动至链表第一位
ps: 使用指针的话，从m拿到*list.Element后就直接找到了链表上的对应节点，如果存放的是值的话需要遍历查找值所在的节点(另外一点，相同的值的节点可能有多个，所以存储值的方式不可取)
第二点: list.Element中无法直接存储key,value,只有一个interface类型的Value，于是需要构造存储k/v的类型，然后将k/v存储为这个值的一个变量，然后再存放至list.Element的Value处

参考
https://www.youtube.com/watch?v=8j4nHj92uRA
https://github.com/aQuaYi/LeetCode-in-Go/blob/master/Algorithms/0146.lru-cache/lru-cache.go
*/
type LRUCache struct {
	cap int
	l   *list.List
	m   map[int]*list.Element //使用指针 共用元素
}

type Pair struct {
	k int
	v int
}

func Constructor(cap int) LRUCache {
	return LRUCache{
		cap: cap,
		l:   list.New(),
		m:   make(map[int]*list.Element, cap),
	}
}

func (c *LRUCache) Get(key int) int {
	if node, ok := c.m[key]; ok {
		c.l.MoveToFront(node)
		return node.Value.(Pair).v
	} else {
		return -1
	}
}

func (c *LRUCache) Put(key int, value int) {
	if node, ok := c.m[key]; ok {
		c.l.MoveToFront(node)
		node.Value = Pair{v: value, k: key} //这里容易犯错 不能写成node.Value.(Pair).v = value 会报错 并且这句容易遗漏
	} else {
		if c.l.Len() == c.cap {
			//容量已满 从链表和map上删除最后一个元素
			removeNode := c.l.Back()
			removeKey := removeNode.Value.(Pair).k
			delete(c.m, removeKey) //这里用到了pair中的key，只有在pair中保存了key 才能删除m中的数据
			c.l.Remove(removeNode)
		}

		//新增元素节点
		v := Pair{k: key, v: value}
		newNode := c.l.PushFront(v) //这里
		c.m[key] = newNode
	}
}

func main() {

	cache := Constructor(2)
	cache.Put(1, 1)
	cache.Put(2, 2)
	fmt.Println(cache.Get(1))
	cache.Put(3, 3)
	fmt.Println(cache.Get(2))
	cache.Put(4, 4) // evicts key 1
	cache.Get(1)    // returns -1 (not found)
	cache.Get(3)    // returns 3
	cache.Get(4)    // returns 4
	fmt.Println(cache.Get(4))
	//3 4
}
